//Tue Feb 22 00:00:34 CST 2011
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

int dp[13000][13000];

int main(int argc, const char* argv[]) {
	freopen("input.in", "r", stdin);
	freopen("output.out", "w", stdout);
	int N, M;
	while (cin >> N >> M) {
		int *w = new int[N];
		int *d = new int[N];
		int **dp = new int[N + 1][M + 1];

		for (int i = 0; i < N; i++) {
			cin >> w[i] >> d[i];
		}
		for (int i = 0; i < M; i++) {
			dp[0][i] = 0;
		}
		for (int i = 0; i < N; i++) {
			dp[i][0] = 0;
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (w[i] + j > M)
					dp[i][j] = dp[i - 1][j];
				else
					dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + d[i]);
			}
		}
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}
